<!DOCTYPE html>
<html lang=en>
<head>
    <!-- so meta -->
    <meta charset="utf-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="HandheldFriendly" content="True">
    <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=5" />
    <meta name="description" content="认识HashMapHashMap是平时开发中常用一种数据结构。其底层精妙的设计大大提高了我们开发出来的产品的底层性能。那么它是如何实现的，我们来一探究竟 底层数据结构JDK1.7及之前 桶数组（bucket） + 链表 JDK1.8之后    当链表达到一定长度时 会转化为红黑树 其实就是哈希散列法中的“拉链法”，只不过当一条链长度过长时，为了增加查询数据的性能，在JDK1.8之后就会将链条树化（">
<meta property="og:type" content="article">
<meta property="og:title" content="HashMap">
<meta property="og:url" content="https://cheung0-bit.github.io/d895167cf8d2/index.html">
<meta property="og:site_name" content="Bruce Zhang&#39;s Blogs">
<meta property="og:description" content="认识HashMapHashMap是平时开发中常用一种数据结构。其底层精妙的设计大大提高了我们开发出来的产品的底层性能。那么它是如何实现的，我们来一探究竟 底层数据结构JDK1.7及之前 桶数组（bucket） + 链表 JDK1.8之后    当链表达到一定长度时 会转化为红黑树 其实就是哈希散列法中的“拉链法”，只不过当一条链长度过长时，为了增加查询数据的性能，在JDK1.8之后就会将链条树化（">
<meta property="og:locale" content="en_US">
<meta property="og:image" content="https://0-bit.oss-cn-beijing.aliyuncs.com/image-20220731133023452.png">
<meta property="og:image" content="https://0-bit.oss-cn-beijing.aliyuncs.com/image-20220731135448439.png">
<meta property="og:image" content="https://0-bit.oss-cn-beijing.aliyuncs.com/image-20220731145208320.png">
<meta property="og:image" content="https://0-bit.oss-cn-beijing.aliyuncs.com/image-20220731145500014.png">
<meta property="og:image" content="https://0-bit.oss-cn-beijing.aliyuncs.com/image-20220819114543226.png">
<meta property="og:image" content="https://0-bit.oss-cn-beijing.aliyuncs.com/image-20220819135919766.png">
<meta property="og:image" content="https://0-bit.oss-cn-beijing.aliyuncs.com/image-20220819144720573.png">
<meta property="article:published_time" content="2022-08-19T13:41:23.000Z">
<meta property="article:modified_time" content="2022-11-25T07:04:14.206Z">
<meta property="article:author" content="张林">
<meta property="article:tag" content="数据结构与算法">
<meta property="article:tag" content="Java">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://0-bit.oss-cn-beijing.aliyuncs.com/image-20220731133023452.png">
    
    
      
        
          <link rel="shortcut icon" href="/images/favicon.ico">
        
      
      
        
          <link rel="icon" type="image/png" href="/images/favicon-192x192.png" sizes="192x192">
        
      
      
        
          <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon.png">
        
      
    
    <!-- title -->
    <title>HashMap</title>
    <!-- styles -->
    
<link rel="stylesheet" href="/css/style.css">

    <!-- persian styles -->
    
    <!-- rss -->
    
    
      <link rel="alternate" href="/atom.xml" title="Bruce Zhang&#39;s Blogs" type="application/atom+xml" />
    
	<!-- mathjax -->
	
<meta name="generator" content="Hexo 7.0.0"></head>

<body class="max-width mx-auto px3 ltr">
    
      <div id="header-post">
  <a id="menu-icon" href="#" aria-label="Menu"><i class="fas fa-bars fa-lg"></i></a>
  <a id="menu-icon-tablet" href="#" aria-label="Menu"><i class="fas fa-bars fa-lg"></i></a>
  <a id="top-icon-tablet" href="#" aria-label="Top" onclick="$('html, body').animate({ scrollTop: 0 }, 'fast');" style="display:none;"><i class="fas fa-chevron-up fa-lg"></i></a>
  <span id="menu">
    <span id="nav">
      <ul>
        <!--
       --><li><a href="/">Home</a></li><!--
     --><!--
       --><li><a href="/about/">About</a></li><!--
     --><!--
       --><li><a href="/archives/">Articles</a></li><!--
     --><!--
       --><li><a href="/categories/">Category</a></li><!--
     --><!--
       --><li><a href="/search/">Search</a></li><!--
     -->
      </ul>
    </span>
    <br/>
    <span id="actions">
      <ul>
        
        <li><a class="icon" aria-label="Previous post" href="/c38d47a6babf/"><i class="fas fa-chevron-left" aria-hidden="true" onmouseover="$('#i-prev').toggle();" onmouseout="$('#i-prev').toggle();"></i></a></li>
        
        
        <li><a class="icon" aria-label="Next post" href="/7cb8dc2a6878/"><i class="fas fa-chevron-right" aria-hidden="true" onmouseover="$('#i-next').toggle();" onmouseout="$('#i-next').toggle();"></i></a></li>
        
        <li><a class="icon" aria-label="Back to top" href="#" onclick="$('html, body').animate({ scrollTop: 0 }, 'fast');"><i class="fas fa-chevron-up" aria-hidden="true" onmouseover="$('#i-top').toggle();" onmouseout="$('#i-top').toggle();"></i></a></li>
        <li><a class="icon" aria-label="Share post" href="#"><i class="fas fa-share-alt" aria-hidden="true" onmouseover="$('#i-share').toggle();" onmouseout="$('#i-share').toggle();" onclick="$('#share').toggle();return false;"></i></a></li>
      </ul>
      <span id="i-prev" class="info" style="display:none;">Previous post</span>
      <span id="i-next" class="info" style="display:none;">Next post</span>
      <span id="i-top" class="info" style="display:none;">Back to top</span>
      <span id="i-share" class="info" style="display:none;">Share post</span>
    </span>
    <br/>
    <div id="share" style="display: none">
      <ul>
  <li><a class="icon" target="_blank" rel="noopener" href="http://www.facebook.com/sharer.php?u=https://cheung0-bit.github.io/d895167cf8d2/"><i class="fab fa-facebook " aria-hidden="true"></i></a></li>
  <li><a class="icon" target="_blank" rel="noopener" href="https://twitter.com/share?url=https://cheung0-bit.github.io/d895167cf8d2/&text=HashMap"><i class="fab fa-twitter " aria-hidden="true"></i></a></li>
  <li><a class="icon" target="_blank" rel="noopener" href="http://www.linkedin.com/shareArticle?url=https://cheung0-bit.github.io/d895167cf8d2/&title=HashMap"><i class="fab fa-linkedin " aria-hidden="true"></i></a></li>
  <li><a class="icon" target="_blank" rel="noopener" href="https://pinterest.com/pin/create/bookmarklet/?url=https://cheung0-bit.github.io/d895167cf8d2/&is_video=false&description=HashMap"><i class="fab fa-pinterest " aria-hidden="true"></i></a></li>
  <li><a class="icon" href="mailto:?subject=HashMap&body=Check out this article: https://cheung0-bit.github.io/d895167cf8d2/"><i class="fas fa-envelope " aria-hidden="true"></i></a></li>
  <li><a class="icon" target="_blank" rel="noopener" href="https://getpocket.com/save?url=https://cheung0-bit.github.io/d895167cf8d2/&title=HashMap"><i class="fab fa-get-pocket " aria-hidden="true"></i></a></li>
  <li><a class="icon" target="_blank" rel="noopener" href="http://reddit.com/submit?url=https://cheung0-bit.github.io/d895167cf8d2/&title=HashMap"><i class="fab fa-reddit " aria-hidden="true"></i></a></li>
  <li><a class="icon" target="_blank" rel="noopener" href="http://www.stumbleupon.com/submit?url=https://cheung0-bit.github.io/d895167cf8d2/&title=HashMap"><i class="fab fa-stumbleupon " aria-hidden="true"></i></a></li>
  <li><a class="icon" target="_blank" rel="noopener" href="http://digg.com/submit?url=https://cheung0-bit.github.io/d895167cf8d2/&title=HashMap"><i class="fab fa-digg " aria-hidden="true"></i></a></li>
  <li><a class="icon" target="_blank" rel="noopener" href="http://www.tumblr.com/share/link?url=https://cheung0-bit.github.io/d895167cf8d2/&name=HashMap&description="><i class="fab fa-tumblr " aria-hidden="true"></i></a></li>
  <li><a class="icon" target="_blank" rel="noopener" href="https://news.ycombinator.com/submitlink?u=https://cheung0-bit.github.io/d895167cf8d2/&t=HashMap"><i class="fab fa-hacker-news " aria-hidden="true"></i></a></li>
</ul>

    </div>
    <div id="toc">
      <ol class="toc"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E8%AE%A4%E8%AF%86HashMap"><span class="toc-number">1.</span> <span class="toc-text">认识HashMap</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%BA%95%E5%B1%82%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84"><span class="toc-number">1.1.</span> <span class="toc-text">底层数据结构</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%9E%84%E9%80%A0%E5%87%BD%E6%95%B0"><span class="toc-number">1.2.</span> <span class="toc-text">构造函数</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E9%97%A8%E9%99%90%E5%80%BC"><span class="toc-number">1.3.</span> <span class="toc-text">门限值</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%88%9D%E5%A7%8B%E5%8C%96%E5%AE%B9%E9%87%8F"><span class="toc-number">1.4.</span> <span class="toc-text">初始化容量</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E8%B4%9F%E8%BD%BD%E5%9B%A0%E5%AD%90"><span class="toc-number">1.5.</span> <span class="toc-text">负载因子</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%89%B0%E5%8A%A8%E5%87%BD%E6%95%B0"><span class="toc-number">1.6.</span> <span class="toc-text">扰动函数</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#HashMap%E5%9F%BA%E6%9C%AC%E6%93%8D%E4%BD%9C%E5%92%8C%E9%81%8D%E5%8E%86"><span class="toc-number">2.</span> <span class="toc-text">HashMap基本操作和遍历</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#4%E7%A7%8D%E9%81%8D%E5%8E%86%E6%96%B9%E5%BC%8F"><span class="toc-number">2.1.</span> <span class="toc-text">4种遍历方式</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%BA%95%E5%B1%82%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E7%9A%84%E6%9E%84%E5%BB%BA"><span class="toc-number">3.</span> <span class="toc-text">底层数据结构的构建</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E8%8A%82%E7%82%B9%E7%B1%BB"><span class="toc-number">3.1.</span> <span class="toc-text">节点类</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%8F%92%E5%85%A5%E8%8A%82%E7%82%B9%E7%9A%84putVal-%E6%96%B9%E6%B3%95"><span class="toc-number">3.2.</span> <span class="toc-text">插入节点的putVal()方法</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#%E5%81%9A%E5%A5%BD%E9%A2%84%E5%A4%87%E5%B7%A5%E4%BD%9C"><span class="toc-number">3.2.1.</span> <span class="toc-text">做好预备工作</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E7%AC%AC%E4%B8%80%E7%A7%8D%E6%83%85%E5%86%B5%EF%BC%88%E5%BD%93%E5%89%8D%E4%BD%8D%E7%BD%AE%E4%B8%BAnull%EF%BC%89"><span class="toc-number">3.2.2.</span> <span class="toc-text">第一种情况（当前位置为null）</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E7%AC%AC%E4%BA%8C%E7%A7%8D%E6%83%85%E5%86%B5%EF%BC%88hash%E5%88%86%E9%85%8D%E7%9A%84%E4%BD%8D%E7%BD%AE%E7%9B%B8%E5%90%8C%E4%B8%94Key%E7%9B%B8%E5%90%8C%EF%BC%89"><span class="toc-number">3.2.3.</span> <span class="toc-text">第二种情况（hash分配的位置相同且Key相同）</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E7%AC%AC%E4%B8%89%E7%A7%8D%E6%83%85%E5%86%B5%EF%BC%88%E5%8A%A0%E5%85%A5%E7%BA%A2%E9%BB%91%E6%A0%91%E8%8A%82%E7%82%B9%EF%BC%89"><span class="toc-number">3.2.4.</span> <span class="toc-text">第三种情况（加入红黑树节点）</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E7%AC%AC%E5%9B%9B%E7%A7%8D%E6%83%85%E5%86%B5%EF%BC%88%E5%8A%A0%E5%85%A5%E9%93%BE%E8%A1%A8%E8%8A%82%E7%82%B9%EF%BC%89"><span class="toc-number">3.2.5.</span> <span class="toc-text">第四种情况（加入链表节点）</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#HashMap%E7%9A%84resize-%E6%96%B9%E6%B3%95"><span class="toc-number">3.3.</span> <span class="toc-text">HashMap的resize()方法</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#%E6%97%A0%E5%8F%82%E6%9E%84%E9%80%A0%E7%9A%84%E7%A9%BAHashMap"><span class="toc-number">3.3.1.</span> <span class="toc-text">无参构造的空HashMap</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E8%BE%BE%E5%88%B0%E9%97%A8%E9%99%90%E5%80%BC%E9%9C%80%E8%A6%81%E6%89%A9%E5%AE%B9"><span class="toc-number">3.3.2.</span> <span class="toc-text">达到门限值需要扩容</span></a><ol class="toc-child"><li class="toc-item toc-level-5"><a class="toc-link" href="#%E6%95%B0%E7%BB%84%E7%9A%84%E8%B0%83%E6%95%B4"><span class="toc-number">3.3.2.1.</span> <span class="toc-text">数组的调整</span></a></li><li class="toc-item toc-level-5"><a class="toc-link" href="#%E9%93%BE%E8%A1%A8%E7%9A%84%E8%B0%83%E6%95%B4"><span class="toc-number">3.3.2.2.</span> <span class="toc-text">链表的调整</span></a></li><li class="toc-item toc-level-5"><a class="toc-link" href="#%E7%BA%A2%E9%BB%91%E6%A0%91%E7%9A%84%E8%B0%83%E6%95%B4"><span class="toc-number">3.3.2.3.</span> <span class="toc-text">红黑树的调整</span></a></li></ol></li></ol></li></ol></li></ol>
    </div>
  </span>
</div>

    
    <div class="content index py4">
        
        <article class="post" itemscope itemtype="http://schema.org/BlogPosting">
  <header>
    
    <h1 class="posttitle" itemprop="name headline">
        HashMap
    </h1>



    <div class="meta">
      <span class="author" itemprop="author" itemscope itemtype="http://schema.org/Person">
        <span itemprop="name">张林</span>
      </span>
      
    <div class="postdate">
      
        <time datetime="2022-08-19T13:41:23.000Z" itemprop="datePublished">2022-08-19</time>
        
        (Updated: <time datetime="2022-11-25T07:04:14.206Z" itemprop="dateModified">2022-11-25</time>)
        
      
    </div>


      
    <div class="article-category">
        <i class="fas fa-archive"></i>
        <a class="category-link" href="/categories/%E9%9D%A2%E8%AF%95/">面试</a> › <a class="category-link" href="/categories/%E9%9D%A2%E8%AF%95/Java/">Java</a>
    </div>


      
    <div class="article-tag">
        <i class="fas fa-tag"></i>
        <a class="tag-link-link" href="/tags/Java/" rel="tag">Java</a>, <a class="tag-link-link" href="/tags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/" rel="tag">数据结构与算法</a>
    </div>


    </div>
  </header>
  

  <div class="content" itemprop="articleBody">
    <h2 id="认识HashMap"><a href="#认识HashMap" class="headerlink" title="认识HashMap"></a>认识HashMap</h2><p>HashMap是平时开发中常用一种数据结构。其底层精妙的设计大大提高了我们开发出来的产品的底层性能。那么它是如何实现的，我们来一探究竟</p>
<h3 id="底层数据结构"><a href="#底层数据结构" class="headerlink" title="底层数据结构"></a>底层数据结构</h3><p>JDK1.7及之前 桶数组（bucket） + 链表</p>
<p>JDK1.8之后    当链表达到一定长度时 会转化为红黑树</p>
<p>其实就是哈希散列法中的“拉链法”，只不过当一条链长度过长时，为了增加查询数据的性能，在JDK1.8之后就会将链条树化（红黑树）</p>
<p><img src="https://0-bit.oss-cn-beijing.aliyuncs.com/image-20220731133023452.png" alt="image-20220731133023452"></p>
<h3 id="构造函数"><a href="#构造函数" class="headerlink" title="构造函数"></a>构造函数</h3><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// 默认构造函数 加载因子为默认值0.75f</span></span><br><span class="line"><span class="keyword">public</span> <span class="title function_">HashMap</span><span class="params">()</span> &#123;</span><br><span class="line">    <span class="built_in">this</span>.loadFactor = DEFAULT_LOAD_FACTOR;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 包含另一个“Map”的构造函数</span></span><br><span class="line"><span class="keyword">public</span> <span class="title function_">HashMap</span><span class="params">(Map&lt;? extends K, ? extends V&gt; m)</span> &#123;</span><br><span class="line">    <span class="built_in">this</span>.loadFactor = DEFAULT_LOAD_FACTOR;</span><br><span class="line">    putMapEntries(m, <span class="literal">false</span>);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 指定了容器大小的构造函数</span></span><br><span class="line"><span class="keyword">public</span> <span class="title function_">HashMap</span><span class="params">(<span class="type">int</span> initialCapacity)</span> &#123;</span><br><span class="line">    <span class="built_in">this</span>(initialCapacity, DEFAULT_LOAD_FACTOR);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="comment">// 指定“容量大小”和“加载因子”的构造函数</span></span><br><span class="line"><span class="keyword">public</span> <span class="title function_">HashMap</span><span class="params">(<span class="type">int</span> initialCapacity, <span class="type">float</span> loadFactor)</span> &#123;</span><br><span class="line">    <span class="keyword">if</span> (initialCapacity &lt; <span class="number">0</span>)</span><br><span class="line">        <span class="keyword">throw</span> <span class="keyword">new</span> <span class="title class_">IllegalArgumentException</span>(<span class="string">&quot;Illegal initial capacity: &quot;</span> + initialCapacity);</span><br><span class="line">    <span class="keyword">if</span> (initialCapacity &gt; MAXIMUM_CAPACITY)</span><br><span class="line">        initialCapacity = MAXIMUM_CAPACITY;</span><br><span class="line">    <span class="keyword">if</span> (loadFactor &lt;= <span class="number">0</span> || Float.isNaN(loadFactor))</span><br><span class="line">        <span class="keyword">throw</span> <span class="keyword">new</span> <span class="title class_">IllegalArgumentException</span>(<span class="string">&quot;Illegal load factor: &quot;</span> + loadFactor);</span><br><span class="line">    <span class="built_in">this</span>.loadFactor = loadFactor;</span><br><span class="line">    <span class="built_in">this</span>.threshold = tableSizeFor(initialCapacity);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>一般常用的就是构建一个空的HashMap，别的构造函数涉及到了一些需要知道的概念，借此机会一次性说掉</p>
<h3 id="门限值"><a href="#门限值" class="headerlink" title="门限值"></a>门限值</h3><p>门限值Threshold就是扩容机制触发的一个阈值 计算公式为：</p>
<p> 门限值 &#x3D; 数组容量 X 负载因子</p>
<p>其中负载因子会在下面做出说明</p>
<h3 id="初始化容量"><a href="#初始化容量" class="headerlink" title="初始化容量"></a>初始化容量</h3><p>指的就是桶数组（bucket）的初始化大小 默认为16</p>
<p>为什么是16呢 简单的解释就是使用2的次方的容量可以在HASH取模运算后使得散列更加均匀 学过数据结构的朋友应该都有印象 书上建议初始化大小为2的次幂 在这里JDK开发者选择了16作为默认的值 </p>
<p>这些说明了为什么扩容时都是乘以2 就是为了保证桶数组的容量为2的次幂</p>
<p>在构造函数中若指定了一个初始的大小 则初始容量会进行计算 找到一个最近的2次幂数</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="built_in">this</span>.threshold = tableSizeFor(initialCapacity);</span><br></pre></td></tr></table></figure>

<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">static</span> <span class="keyword">final</span> <span class="type">int</span> <span class="title function_">tableSizeFor</span><span class="params">(<span class="type">int</span> cap)</span> &#123;</span><br><span class="line">    <span class="type">int</span> <span class="variable">n</span> <span class="operator">=</span> cap - <span class="number">1</span>;</span><br><span class="line">    n |= n &gt;&gt;&gt; <span class="number">1</span>;</span><br><span class="line">    n |= n &gt;&gt;&gt; <span class="number">2</span>;</span><br><span class="line">    n |= n &gt;&gt;&gt; <span class="number">4</span>;</span><br><span class="line">    n |= n &gt;&gt;&gt; <span class="number">8</span>;</span><br><span class="line">    n |= n &gt;&gt;&gt; <span class="number">16</span>;</span><br><span class="line">    <span class="keyword">return</span> (n &lt; <span class="number">0</span>) ? <span class="number">1</span> : (n &gt;= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + <span class="number">1</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>乍看是不是很懵逼 这个算法十分精妙 来理解一下</p>
<p>比如要求17对应的2次幂数 易得出是32</p>
<p>那么这个算法如何实现的呢  就是先将17 -1 得到 16 二进制就是 <code>10000</code> </p>
<p>只要将二进制数第一个为1的位置开始，后面的数字全变为1 最后再加上1  就是我们要的2次幂数了 <code>10000</code> -&gt; <code>11111(31)</code> -&gt; <code>31 + 1</code> -&gt; <code>32</code></p>
<p>这个算法就是实现将后面数全变为1的操作 那为什么是逻辑右移1，2，4，8，16 就结束了呢 </p>
<p>这样思考 一个位置为1 右移1位 就得到了两个1 此时右移2位 就得到了4各个1 以此类推 当右移16位时 刚好一个int类型位数操作完 自然可以得到任何int类型数据的所要求的二次幂数</p>
<h3 id="负载因子"><a href="#负载因子" class="headerlink" title="负载因子"></a>负载因子</h3><p>负载因子可以自定义，默认为0.75f</p>
<p>该参数用于调节散列效果 例如当负载因子为1时 数组需要到达容量大小则才开始扩容 不可避免会出现很多HASH冲突 导致某个节点的链条过长 影响查询性能 当负载因子为0.5时 每当数组容量使用了一半时就开始扩容了 虽然会大大降低HASH冲突的概率 但散列效果却会不尽如人意 于是取中间值0.75作为默认的负载因子 开发者可以根据需求 自由调节</p>
<h3 id="扰动函数"><a href="#扰动函数" class="headerlink" title="扰动函数"></a>扰动函数</h3><p>HashMap中有这样一个方法专门用于求键值的HASH值</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">static</span> <span class="keyword">final</span> <span class="type">int</span> <span class="title function_">hash</span><span class="params">(Object key)</span> &#123;</span><br><span class="line">    <span class="type">int</span> h;</span><br><span class="line">    <span class="keyword">return</span> (key == <span class="literal">null</span>) ? <span class="number">0</span> : (h = key.hashCode()) ^ (h &gt;&gt;&gt; <span class="number">16</span>);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>可见，在key求<code>hashcode</code>之后又将其与自己逻辑右移16位后的结果做了按位与操作，那么有两个问题</p>
<ul>
<li>为什么要做按位与<ul>
<li>保留<code>hashcode</code>的结果特征 增强散列效果</li>
</ul>
</li>
<li>为什么是16位<ul>
<li>因为<code>hashcode</code>表示数据范围是int类型数据范围 众所周知 int由32个bit组成 因此逻辑右移16位（一半距离） 以此结合一个<code>hashcode</code>高位和低位的特征 以降低在对桶数组容量取模运算后的hash冲突</li>
</ul>
</li>
</ul>
<p><img src="https://0-bit.oss-cn-beijing.aliyuncs.com/image-20220731135448439.png" alt="image-20220731135448439"></p>
<blockquote>
<p>个人理解：这些参数的存在，就是为了数据有一个较好的散列效果，以增强数据查询插入的效率，以达到高性能的效果</p>
</blockquote>
<h2 id="HashMap基本操作和遍历"><a href="#HashMap基本操作和遍历" class="headerlink" title="HashMap基本操作和遍历"></a>HashMap基本操作和遍历</h2><p>先循环插入一些数</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line">HashMap&lt;Integer, Integer&gt; map = <span class="keyword">new</span> <span class="title class_">HashMap</span>&lt;&gt;();</span><br><span class="line"><span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> <span class="number">0</span>; i &lt; <span class="number">14</span>; i++) &#123;</span><br><span class="line">    map.put(i, (<span class="type">int</span>) (Math.random() * <span class="number">100</span>));</span><br><span class="line">&#125;</span><br><span class="line">System.out.println(<span class="string">&quot;直接输出HashMap&quot;</span>);</span><br><span class="line">System.out.println(map);</span><br></pre></td></tr></table></figure>

<figure class="highlight txt"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">直接输出HashMap</span><br><span class="line">&#123;0=43, 1=14, 2=54, 3=22, 4=75, 5=36, 6=73, 7=37, 8=46, 9=77, 10=69, 11=23, 12=63, 13=85&#125;</span><br></pre></td></tr></table></figure>

<p>这里可见HashMap以键值对的形式返回了数据</p>
<h3 id="4种遍历方式"><a href="#4种遍历方式" class="headerlink" title="4种遍历方式"></a>4种遍历方式</h3><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// ====ForEach循环遍历====</span></span><br><span class="line">System.out.println(<span class="string">&quot;Iterate entries using ForEach loop:&quot;</span>);</span><br><span class="line"><span class="keyword">for</span> (Map.Entry&lt;Integer, Integer&gt; stringStringEntry : map.entrySet()) &#123;</span><br><span class="line">    System.out.println(<span class="string">&quot;Key = &quot;</span> + stringStringEntry.getKey() + <span class="string">&quot;, Value = &quot;</span> + stringStringEntry.getValue());</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="comment">// ====ForEach迭代键值对方式====</span></span><br><span class="line">System.out.println(<span class="string">&quot;Iterate keys / values using ForEach loop:&quot;</span>);</span><br><span class="line"><span class="keyword">for</span> (Integer key : map.keySet()) &#123;</span><br><span class="line">    System.out.println(<span class="string">&quot;Key=&quot;</span> + key);</span><br><span class="line">&#125;</span><br><span class="line"><span class="keyword">for</span> (Integer value : map.values()) &#123;</span><br><span class="line">    System.out.println(<span class="string">&quot;Value=&quot;</span> + value);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="comment">// ====迭代器遍历===</span></span><br><span class="line">System.out.println(<span class="string">&quot;Iterate using Iterator with generics=v:&quot;</span>);</span><br><span class="line">Iterator&lt;Map.Entry&lt;Integer, Integer&gt;&gt; iterator = map.entrySet().iterator();</span><br><span class="line"><span class="keyword">while</span> (iterator.hasNext()) &#123;</span><br><span class="line">    Map.Entry&lt;Integer, Integer&gt; entry = iterator.next();</span><br><span class="line">    System.out.println(<span class="string">&quot;Key=&quot;</span> + entry.getKey() + <span class="string">&quot; Value=&quot;</span> + entry.getValue());</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="comment">// ====Java Lambda表达式遍历====</span></span><br><span class="line">System.out.println(<span class="string">&quot;Iterate using Java 8 Lambda Expression:&quot;</span>);</span><br><span class="line">map.forEach((K, V) -&gt; System.out.println(<span class="string">&quot;key: &quot;</span> + K + <span class="string">&quot; value:&quot;</span> + V));</span><br></pre></td></tr></table></figure>

<p>打印结果太多 就不展示了 可以自己试一下 个人觉得Lambda表达式简直爱了好吗 Elegant And Concise 优雅且简洁</p>
<h2 id="底层数据结构的构建"><a href="#底层数据结构的构建" class="headerlink" title="底层数据结构的构建"></a>底层数据结构的构建</h2><p>下面就来看看所谓的桶数组+链表+红黑树到底是怎么构建 让我们一起撕开神秘的面纱</p>
<h3 id="节点类"><a href="#节点类" class="headerlink" title="节点类"></a>节点类</h3><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">static</span> <span class="keyword">class</span> <span class="title class_">Node</span>&lt;K,V&gt; <span class="keyword">implements</span> <span class="title class_">Map</span>.Entry&lt;K,V&gt; &#123;</span><br><span class="line">    <span class="keyword">final</span> <span class="type">int</span> hash;</span><br><span class="line">    <span class="keyword">final</span> K key;</span><br><span class="line">    V value;</span><br><span class="line">    Node&lt;K,V&gt; next;</span><br><span class="line"></span><br><span class="line">    Node(<span class="type">int</span> hash, K key, V value, Node&lt;K,V&gt; next) &#123;</span><br><span class="line">        <span class="built_in">this</span>.hash = hash;</span><br><span class="line">        <span class="built_in">this</span>.key = key;</span><br><span class="line">        <span class="built_in">this</span>.value = value;</span><br><span class="line">        <span class="built_in">this</span>.next = next;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">public</span> <span class="keyword">final</span> K <span class="title function_">getKey</span><span class="params">()</span>        &#123; <span class="keyword">return</span> key; &#125;</span><br><span class="line">    <span class="keyword">public</span> <span class="keyword">final</span> V <span class="title function_">getValue</span><span class="params">()</span>      &#123; <span class="keyword">return</span> value; &#125;</span><br><span class="line">    <span class="keyword">public</span> <span class="keyword">final</span> String <span class="title function_">toString</span><span class="params">()</span> &#123; <span class="keyword">return</span> key + <span class="string">&quot;=&quot;</span> + value; &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">public</span> <span class="keyword">final</span> <span class="type">int</span> <span class="title function_">hashCode</span><span class="params">()</span> &#123;</span><br><span class="line">        <span class="keyword">return</span> Objects.hashCode(key) ^ Objects.hashCode(value);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">public</span> <span class="keyword">final</span> V <span class="title function_">setValue</span><span class="params">(V newValue)</span> &#123;</span><br><span class="line">        <span class="type">V</span> <span class="variable">oldValue</span> <span class="operator">=</span> value;</span><br><span class="line">        value = newValue;</span><br><span class="line">        <span class="keyword">return</span> oldValue;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">public</span> <span class="keyword">final</span> <span class="type">boolean</span> <span class="title function_">equals</span><span class="params">(Object o)</span> &#123;</span><br><span class="line">        <span class="keyword">if</span> (o == <span class="built_in">this</span>)</span><br><span class="line">            <span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">        <span class="keyword">if</span> (o <span class="keyword">instanceof</span> Map.Entry) &#123;</span><br><span class="line">            Map.Entry&lt;?,?&gt; e = (Map.Entry&lt;?,?&gt;)o;</span><br><span class="line">            <span class="keyword">if</span> (Objects.equals(key, e.getKey()) &amp;&amp;</span><br><span class="line">                Objects.equals(value, e.getValue()))</span><br><span class="line">                <span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>这便是HashMap中最基本的一个节点的构成 它实现了<code>Map.Entry&lt;K,V&gt;</code> Entry是Map的一个静态内部类，用于存放键值对</p>
<p>值得注意的是，这里Node的equals方法，是比较Key和Value的equals方法，在开发中，如果有需求要进行个性化的比较，就需要重写我们自己的Object类的equals方法了</p>
<h3 id="插入节点的putVal-方法"><a href="#插入节点的putVal-方法" class="headerlink" title="插入节点的putVal()方法"></a>插入节点的putVal()方法</h3><p>此方法是一个内部方法，仅在内部调用。在我们插入一个节点时，就会调用该方法</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> V <span class="title function_">put</span><span class="params">(K key, V value)</span> &#123;</span><br><span class="line">    <span class="keyword">return</span> putVal(hash(key), key, value, <span class="literal">false</span>, <span class="literal">true</span>);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>putVal方法也详细的展示了怎么构建这么一个精妙的数据结构的</p>
<p>先上源码 前方高能~~~</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">final</span> V <span class="title function_">putVal</span><span class="params">(<span class="type">int</span> hash, K key, V value, <span class="type">boolean</span> onlyIfAbsent,</span></span><br><span class="line"><span class="params">               <span class="type">boolean</span> evict)</span> &#123;</span><br><span class="line">    Node&lt;K,V&gt;[] tab; Node&lt;K,V&gt; p; <span class="type">int</span> n, i;</span><br><span class="line">    <span class="keyword">if</span> ((tab = table) == <span class="literal">null</span> || (n = tab.length) == <span class="number">0</span>)</span><br><span class="line">        n = (tab = resize()).length;</span><br><span class="line">    <span class="keyword">if</span> ((p = tab[i = (n - <span class="number">1</span>) &amp; hash]) == <span class="literal">null</span>)</span><br><span class="line">        tab[i] = newNode(hash, key, value, <span class="literal">null</span>);</span><br><span class="line">    <span class="keyword">else</span> &#123;</span><br><span class="line">        Node&lt;K,V&gt; e; K k;</span><br><span class="line">        <span class="keyword">if</span> (p.hash == hash &amp;&amp;</span><br><span class="line">            ((k = p.key) == key || (key != <span class="literal">null</span> &amp;&amp; key.equals(k))))</span><br><span class="line">            e = p;</span><br><span class="line">        <span class="keyword">else</span> <span class="keyword">if</span> (p <span class="keyword">instanceof</span> TreeNode)</span><br><span class="line">            e = ((TreeNode&lt;K,V&gt;)p).putTreeVal(<span class="built_in">this</span>, tab, hash, key, value);</span><br><span class="line">        <span class="keyword">else</span> &#123;</span><br><span class="line">            <span class="keyword">for</span> (<span class="type">int</span> <span class="variable">binCount</span> <span class="operator">=</span> <span class="number">0</span>; ; ++binCount) &#123;</span><br><span class="line">                <span class="keyword">if</span> ((e = p.next) == <span class="literal">null</span>) &#123;</span><br><span class="line">                    p.next = newNode(hash, key, value, <span class="literal">null</span>);</span><br><span class="line">                    <span class="keyword">if</span> (binCount &gt;= TREEIFY_THRESHOLD - <span class="number">1</span>) <span class="comment">// -1 for 1st</span></span><br><span class="line">                        treeifyBin(tab, hash);</span><br><span class="line">                    <span class="keyword">break</span>;</span><br><span class="line">                &#125;</span><br><span class="line">                <span class="keyword">if</span> (e.hash == hash &amp;&amp;</span><br><span class="line">                    ((k = e.key) == key || (key != <span class="literal">null</span> &amp;&amp; key.equals(k))))</span><br><span class="line">                    <span class="keyword">break</span>;</span><br><span class="line">                p = e;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> (e != <span class="literal">null</span>) &#123; <span class="comment">// existing mapping for key</span></span><br><span class="line">            <span class="type">V</span> <span class="variable">oldValue</span> <span class="operator">=</span> e.value;</span><br><span class="line">            <span class="keyword">if</span> (!onlyIfAbsent || oldValue == <span class="literal">null</span>)</span><br><span class="line">                e.value = value;</span><br><span class="line">            afterNodeAccess(e);</span><br><span class="line">            <span class="keyword">return</span> oldValue;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    ++modCount;</span><br><span class="line">    <span class="keyword">if</span> (++size &gt; threshold)</span><br><span class="line">        resize();</span><br><span class="line">    afterNodeInsertion(evict);</span><br><span class="line">    <span class="keyword">return</span> <span class="literal">null</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>头疼的来了 看看怎么拆解 怎么理解</p>
<h4 id="做好预备工作"><a href="#做好预备工作" class="headerlink" title="做好预备工作"></a>做好预备工作</h4><p><img src="https://0-bit.oss-cn-beijing.aliyuncs.com/image-20220731145208320.png" alt="image-20220731145208320"></p>
<p>这里进行一系列的初始化 tab即是桶数组容器 p就是插入的单个节点 若一上来table为null 则说明HashMap仅仅是做了初始化 还没有一个初始化的大小空间  那么就resize()方法分配初始空间 这里只要知道resize方法就是用来分配空间的 具体细节后面会做分析</p>
<p><img src="https://0-bit.oss-cn-beijing.aliyuncs.com/image-20220731145500014.png" alt="image-20220731145500014"></p>
<h4 id="第一种情况（当前位置为null）"><a href="#第一种情况（当前位置为null）" class="headerlink" title="第一种情况（当前位置为null）"></a>第一种情况（当前位置为null）</h4><p>HASH分配到的偏移位置还没有插入节点，那么二话不说，直接塞入新节点</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">if</span> ((p = tab[i = (n - <span class="number">1</span>) &amp; hash]) == <span class="literal">null</span>)</span><br><span class="line">    tab[i] = newNode(hash, key, value, <span class="literal">null</span>);</span><br></pre></td></tr></table></figure>

<p>值得注意的是 数组偏移是通过 (n - 1) &amp; hash 得到的 其实 这就是将hash对数组容量做了一个取默运算 只不过数组偏移是从0开始的 所以是n-1 非常精妙</p>
<h4 id="第二种情况（hash分配的位置相同且Key相同）"><a href="#第二种情况（hash分配的位置相同且Key相同）" class="headerlink" title="第二种情况（hash分配的位置相同且Key相同）"></a>第二种情况（hash分配的位置相同且Key相同）</h4><p>说明这是节点更新，直接将当前节点更新</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">if</span> (p.hash == hash &amp;&amp;</span><br><span class="line">    ((k = p.key) == key || (key != <span class="literal">null</span> &amp;&amp; key.equals(k))))</span><br><span class="line">    e = p;</span><br></pre></td></tr></table></figure>

<h4 id="第三种情况（加入红黑树节点）"><a href="#第三种情况（加入红黑树节点）" class="headerlink" title="第三种情况（加入红黑树节点）"></a>第三种情况（加入红黑树节点）</h4><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">else</span> <span class="keyword">if</span> (p <span class="keyword">instanceof</span> TreeNode)</span><br><span class="line">    e = ((TreeNode&lt;K,V&gt;)p).putTreeVal(<span class="built_in">this</span>, tab, hash, key, value);</span><br></pre></td></tr></table></figure>

<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">final</span> TreeNode&lt;K,V&gt; <span class="title function_">putTreeVal</span><span class="params">(HashMap&lt;K,V&gt; map, Node&lt;K,V&gt;[] tab,</span></span><br><span class="line"><span class="params">                               <span class="type">int</span> h, K k, V v)</span> &#123;</span><br><span class="line">    Class&lt;?&gt; kc = <span class="literal">null</span>;</span><br><span class="line">    <span class="type">boolean</span> <span class="variable">searched</span> <span class="operator">=</span> <span class="literal">false</span>;</span><br><span class="line">    TreeNode&lt;K,V&gt; root = (parent != <span class="literal">null</span>) ? root() : <span class="built_in">this</span>;</span><br><span class="line">    <span class="keyword">for</span> (TreeNode&lt;K,V&gt; p = root;;) &#123;</span><br><span class="line">        <span class="type">int</span> dir, ph; K pk;</span><br><span class="line">        <span class="keyword">if</span> ((ph = p.hash) &gt; h)</span><br><span class="line">            dir = -<span class="number">1</span>;</span><br><span class="line">        <span class="keyword">else</span> <span class="keyword">if</span> (ph &lt; h)</span><br><span class="line">            dir = <span class="number">1</span>;</span><br><span class="line">        <span class="keyword">else</span> <span class="keyword">if</span> ((pk = p.key) == k || (k != <span class="literal">null</span> &amp;&amp; k.equals(pk)))</span><br><span class="line">            <span class="keyword">return</span> p;</span><br><span class="line">        <span class="keyword">else</span> <span class="keyword">if</span> ((kc == <span class="literal">null</span> &amp;&amp;</span><br><span class="line">                  (kc = comparableClassFor(k)) == <span class="literal">null</span>) ||</span><br><span class="line">                 (dir = compareComparables(kc, k, pk)) == <span class="number">0</span>) &#123;</span><br><span class="line">            <span class="keyword">if</span> (!searched) &#123;</span><br><span class="line">                TreeNode&lt;K,V&gt; q, ch;</span><br><span class="line">                searched = <span class="literal">true</span>;</span><br><span class="line">                <span class="keyword">if</span> (((ch = p.left) != <span class="literal">null</span> &amp;&amp;</span><br><span class="line">                     (q = ch.find(h, k, kc)) != <span class="literal">null</span>) ||</span><br><span class="line">                    ((ch = p.right) != <span class="literal">null</span> &amp;&amp;</span><br><span class="line">                     (q = ch.find(h, k, kc)) != <span class="literal">null</span>))</span><br><span class="line">                    <span class="keyword">return</span> q;</span><br><span class="line">            &#125;</span><br><span class="line">            dir = tieBreakOrder(k, pk);</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        TreeNode&lt;K,V&gt; xp = p;</span><br><span class="line">        <span class="keyword">if</span> ((p = (dir &lt;= <span class="number">0</span>) ? p.left : p.right) == <span class="literal">null</span>) &#123;</span><br><span class="line">            Node&lt;K,V&gt; xpn = xp.next;</span><br><span class="line">            TreeNode&lt;K,V&gt; x = map.newTreeNode(h, k, v, xpn);</span><br><span class="line">            <span class="keyword">if</span> (dir &lt;= <span class="number">0</span>)</span><br><span class="line">                xp.left = x;</span><br><span class="line">            <span class="keyword">else</span></span><br><span class="line">                xp.right = x;</span><br><span class="line">            xp.next = x;</span><br><span class="line">            x.parent = x.prev = xp;</span><br><span class="line">            <span class="keyword">if</span> (xpn != <span class="literal">null</span>)</span><br><span class="line">                ((TreeNode&lt;K,V&gt;)xpn).prev = x;</span><br><span class="line">            moveRootToFront(tab, balanceInsertion(root, x));</span><br><span class="line">            <span class="keyword">return</span> <span class="literal">null</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>具体怎么加入的，需要先了解红黑树，这里不做多说明</p>
<h4 id="第四种情况（加入链表节点）"><a href="#第四种情况（加入链表节点）" class="headerlink" title="第四种情况（加入链表节点）"></a>第四种情况（加入链表节点）</h4><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">else</span> &#123;</span><br><span class="line">    <span class="keyword">for</span> (<span class="type">int</span> <span class="variable">binCount</span> <span class="operator">=</span> <span class="number">0</span>; ; ++binCount) &#123;</span><br><span class="line">        <span class="keyword">if</span> ((e = p.next) == <span class="literal">null</span>) &#123;</span><br><span class="line">            p.next = newNode(hash, key, value, <span class="literal">null</span>);</span><br><span class="line">            <span class="keyword">if</span> (binCount &gt;= TREEIFY_THRESHOLD - <span class="number">1</span>) <span class="comment">// -1 for 1st</span></span><br><span class="line">                treeifyBin(tab, hash);</span><br><span class="line">            <span class="keyword">break</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> (e.hash == hash </span><br><span class="line">            ((k = e.key) == key || (key != <span class="literal">null</span> &amp;&amp; key.equals(k))))</span><br><span class="line">            <span class="keyword">break</span>;</span><br><span class="line">        p = e;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>遍历链表，若hash值Key值均一样，则直接退出循环</p>
<p>若链表长度即将大于树化的门槛值，则要靠考虑进行树化</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">final</span> <span class="keyword">void</span> <span class="title function_">treeifyBin</span><span class="params">(Node&lt;K,V&gt;[] tab, <span class="type">int</span> hash)</span> &#123;</span><br><span class="line">    <span class="type">int</span> n, index; Node&lt;K,V&gt; e;</span><br><span class="line">    <span class="keyword">if</span> (tab == <span class="literal">null</span> || (n = tab.length) &lt; MIN_TREEIFY_CAPACITY)</span><br><span class="line">        resize();</span><br><span class="line">    <span class="keyword">else</span> <span class="keyword">if</span> ((e = tab[index = (n - <span class="number">1</span>) &amp; hash]) != <span class="literal">null</span>) &#123;</span><br><span class="line">        TreeNode&lt;K,V&gt; hd = <span class="literal">null</span>, tl = <span class="literal">null</span>;</span><br><span class="line">        <span class="keyword">do</span> &#123;</span><br><span class="line">            TreeNode&lt;K,V&gt; p = replacementTreeNode(e, <span class="literal">null</span>);</span><br><span class="line">            <span class="keyword">if</span> (tl == <span class="literal">null</span>)</span><br><span class="line">                hd = p;</span><br><span class="line">            <span class="keyword">else</span> &#123;</span><br><span class="line">                p.prev = tl;</span><br><span class="line">                tl.next = p;</span><br><span class="line">            &#125;</span><br><span class="line">            tl = p;</span><br><span class="line">        &#125; <span class="keyword">while</span> ((e = e.next) != <span class="literal">null</span>);</span><br><span class="line">        <span class="keyword">if</span> ((tab[index] = hd) != <span class="literal">null</span>)</span><br><span class="line">            hd.treeify(tab);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>首先会判断桶数组容量是否达到可以树化的最低标准，没有则先进行桶数组的扩容再HASH，达到了则将链表转化为红黑树</p>
<h3 id="HashMap的resize-方法"><a href="#HashMap的resize-方法" class="headerlink" title="HashMap的resize()方法"></a>HashMap的resize()方法</h3><p>在HashMap中，采用二次方扩容法</p>
<p>当HashMap在元素达到负载因子阈值时，便会自动扩容，以保证HASH得到很好的散列</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line">Node&lt;K,V&gt;[] oldTab = table;</span><br><span class="line"><span class="type">int</span> <span class="variable">oldCap</span> <span class="operator">=</span> (oldTab == <span class="literal">null</span>) ? <span class="number">0</span> : oldTab.length;</span><br><span class="line"><span class="type">int</span> <span class="variable">oldThr</span> <span class="operator">=</span> threshold;</span><br><span class="line"><span class="type">int</span> newCap, newThr = <span class="number">0</span>;</span><br></pre></td></tr></table></figure>

<p><code>resize()</code>方法的一开始，进行一系列的初始化。下面分种情况来讨论</p>
<h4 id="无参构造的空HashMap"><a href="#无参构造的空HashMap" class="headerlink" title="无参构造的空HashMap"></a>无参构造的空HashMap</h4><p>由于是一个空的HashMap，<code>oldTable</code> <code>oldCap</code> <code>oldThr</code>均为空</p>
<p><img src="https://0-bit.oss-cn-beijing.aliyuncs.com/image-20220819114543226.png" alt="image-20220819114543226"></p>
<p>于是直接初始化容量为16，门限值为0.75*16 &#x3D; 12</p>
<h4 id="达到门限值需要扩容"><a href="#达到门限值需要扩容" class="headerlink" title="达到门限值需要扩容"></a>达到门限值需要扩容</h4><p><img src="https://0-bit.oss-cn-beijing.aliyuncs.com/image-20220819135919766.png" alt="image-20220819135919766"></p>
<ul>
<li>如果原来的桶数组大小已经超过最大限定容量(1 &lt;&lt; 30)了，那么将门限值设定为Integer数据类型的最大值（1 &lt;&lt; 31）</li>
<li>否则，就直接按照2次幂扩展规则，将桶数组容量和门限值都扩大为原先的2倍</li>
</ul>
<p>接着，不可避免的，需要rehash</p>
<p>大概结构如下：遍历每个节点，进行调整</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">for</span> (<span class="type">int</span> <span class="variable">j</span> <span class="operator">=</span> <span class="number">0</span>; j &lt; oldCap; ++j) &#123;</span><br><span class="line">    Node&lt;K,V&gt; e;</span><br><span class="line">    <span class="keyword">if</span> ((e = oldTab[j]) != <span class="literal">null</span>) &#123;</span><br><span class="line">        oldTab[j] = <span class="literal">null</span>;</span><br><span class="line">        <span class="keyword">if</span> (e.next == <span class="literal">null</span>)</span><br><span class="line">            newTab[e.hash &amp; (newCap - <span class="number">1</span>)] = e;</span><br><span class="line">        <span class="keyword">else</span> <span class="keyword">if</span> (e <span class="keyword">instanceof</span> TreeNode)</span><br><span class="line">            ((TreeNode&lt;K,V&gt;)e).split(<span class="built_in">this</span>, newTab, j, oldCap);</span><br><span class="line">        <span class="keyword">else</span> &#123; <span class="comment">// preserve order</span></span><br><span class="line">            Node&lt;K,V&gt; loHead = <span class="literal">null</span>, loTail = <span class="literal">null</span>;</span><br><span class="line">            <span class="comment">// 一系列操作</span></span><br><span class="line">           	......</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h5 id="数组的调整"><a href="#数组的调整" class="headerlink" title="数组的调整"></a>数组的调整</h5><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">if</span> ((e = oldTab[j]) != <span class="literal">null</span>) &#123;</span><br><span class="line">    oldTab[j] = <span class="literal">null</span>;  <span class="comment">// 这一步将原数组对应位置的节点设为NULL</span></span><br><span class="line">    <span class="keyword">if</span> (e.next == <span class="literal">null</span>)  <span class="comment">// 如果该节点的下一个为空，则说明此处既不是链表，也不是红黑树，直接进行哈希再分配</span></span><br><span class="line">        newTab[e.hash &amp; (newCap - <span class="number">1</span>)] = e;</span><br><span class="line">  	......</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h5 id="链表的调整"><a href="#链表的调整" class="headerlink" title="链表的调整"></a>链表的调整</h5><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">if</span> ((e = oldTab[j]) != <span class="literal">null</span>) &#123;</span><br><span class="line">    oldTab[j] = <span class="literal">null</span>;</span><br><span class="line">    <span class="comment">// 单个节点</span></span><br><span class="line">    ......</span><br><span class="line">    <span class="comment">// 红黑树</span></span><br><span class="line">    ......</span><br><span class="line">    <span class="comment">// 链表</span></span><br><span class="line">    <span class="keyword">else</span> &#123; <span class="comment">// preserve order</span></span><br><span class="line">        Node&lt;K,V&gt; loHead = <span class="literal">null</span>, loTail = <span class="literal">null</span>;</span><br><span class="line">        Node&lt;K,V&gt; hiHead = <span class="literal">null</span>, hiTail = <span class="literal">null</span>;</span><br><span class="line">        Node&lt;K,V&gt; next;</span><br><span class="line">        <span class="keyword">do</span> &#123;</span><br><span class="line">            next = e.next;</span><br><span class="line">            <span class="keyword">if</span> ((e.hash &amp; oldCap) == <span class="number">0</span>) &#123;</span><br><span class="line">                <span class="keyword">if</span> (loTail == <span class="literal">null</span>)</span><br><span class="line">                    loHead = e;</span><br><span class="line">                <span class="keyword">else</span></span><br><span class="line">                    loTail.next = e;</span><br><span class="line">                loTail = e;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">else</span> &#123;</span><br><span class="line">                <span class="keyword">if</span> (hiTail == <span class="literal">null</span>)</span><br><span class="line">                    hiHead = e;</span><br><span class="line">                <span class="keyword">else</span></span><br><span class="line">                    hiTail.next = e;</span><br><span class="line">                hiTail = e;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125; <span class="keyword">while</span> ((e = next) != <span class="literal">null</span>);</span><br><span class="line">        <span class="keyword">if</span> (loTail != <span class="literal">null</span>) &#123;</span><br><span class="line">            loTail.next = <span class="literal">null</span>;</span><br><span class="line">            newTab[j] = loHead;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> (hiTail != <span class="literal">null</span>) &#123;</span><br><span class="line">            hiTail.next = <span class="literal">null</span>;</span><br><span class="line">            newTab[j + oldCap] = hiHead;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>乍一看很复杂，是的。</p>
<p>首先，要明白高低位链表是什么：</p>
<p>将每个节点HASH值与oldCap按位与，如果为0，则加入低位链表，如果高位为1，则加入高位链表</p>
<p>为什么会这样呢，举个例子，oldCap为16</p>
<p>若7(00111) &amp; 16(10000) &#x3D;&gt; 00000 则加入低位链表</p>
<p>若17(10001) &amp; 16(10000) &#x3D;&gt; 10000 则加入高位链表</p>
<p>下面看看怎么通过循环构建两根链表</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">do</span> &#123;</span><br><span class="line">    next = e.next;</span><br><span class="line">    <span class="keyword">if</span> ((e.hash &amp; oldCap) == <span class="number">0</span>) &#123;</span><br><span class="line">        <span class="keyword">if</span> (loTail == <span class="literal">null</span>)</span><br><span class="line">            loHead = e;</span><br><span class="line">        <span class="keyword">else</span></span><br><span class="line">            loTail.next = e;</span><br><span class="line">        loTail = e;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">else</span> &#123;</span><br><span class="line">        <span class="keyword">if</span> (hiTail == <span class="literal">null</span>)</span><br><span class="line">            hiHead = e;</span><br><span class="line">        <span class="keyword">else</span></span><br><span class="line">            hiTail.next = e;</span><br><span class="line">        hiTail = e;</span><br><span class="line">    &#125;</span><br><span class="line">&#125; <span class="keyword">while</span> ((e = next) != <span class="literal">null</span>);</span><br></pre></td></tr></table></figure>

<p>将<code>loHead</code> <code>loTail</code>分别指向低位链表的头尾节点</p>
<p>将<code>hiHead</code> <code>hiTail</code>分别指向高位链表的头尾节点</p>
<p>接着将两条链表加入新的桶数组中</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">if</span> (loTail != <span class="literal">null</span>) &#123;</span><br><span class="line">    loTail.next = <span class="literal">null</span>;</span><br><span class="line">    newTab[j] = loHead;</span><br><span class="line">&#125;</span><br><span class="line"><span class="keyword">if</span> (hiTail != <span class="literal">null</span>) &#123;</span><br><span class="line">    hiTail.next = <span class="literal">null</span>;</span><br><span class="line">    newTab[j + oldCap] = hiHead;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>最后，借互联网上的一张图来帮助理解</p>
<p><img src="https://0-bit.oss-cn-beijing.aliyuncs.com/image-20220819144720573.png" alt="image-20220819144720573"></p>
<h5 id="红黑树的调整"><a href="#红黑树的调整" class="headerlink" title="红黑树的调整"></a>红黑树的调整</h5><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">if</span> ((e = oldTab[j]) != <span class="literal">null</span>) &#123;</span><br><span class="line">    oldTab[j] = <span class="literal">null</span>;</span><br><span class="line">    <span class="comment">// 单节点</span></span><br><span class="line">    ......</span><br><span class="line">    <span class="comment">// 红黑树</span></span><br><span class="line">    <span class="keyword">else</span> <span class="keyword">if</span> (e <span class="keyword">instanceof</span> TreeNode)</span><br><span class="line">        ((TreeNode&lt;K,V&gt;)e).split(<span class="built_in">this</span>, newTab, j, oldCap);</span><br><span class="line">   <span class="comment">// 链表</span></span><br><span class="line">    ......</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>其中split函数细节为：</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">final</span> <span class="keyword">void</span> <span class="title function_">split</span><span class="params">(HashMap&lt;K,V&gt; map, Node&lt;K,V&gt;[] tab, <span class="type">int</span> index, <span class="type">int</span> bit)</span> &#123;</span><br><span class="line">    TreeNode&lt;K,V&gt; b = <span class="built_in">this</span>;</span><br><span class="line">    <span class="comment">// Relink into lo and hi lists, preserving order</span></span><br><span class="line">    TreeNode&lt;K,V&gt; loHead = <span class="literal">null</span>, loTail = <span class="literal">null</span>;</span><br><span class="line">    TreeNode&lt;K,V&gt; hiHead = <span class="literal">null</span>, hiTail = <span class="literal">null</span>;</span><br><span class="line">    <span class="type">int</span> <span class="variable">lc</span> <span class="operator">=</span> <span class="number">0</span>, hc = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span> (TreeNode&lt;K,V&gt; e = b, next; e != <span class="literal">null</span>; e = next) &#123;</span><br><span class="line">        next = (TreeNode&lt;K,V&gt;)e.next;</span><br><span class="line">        e.next = <span class="literal">null</span>;</span><br><span class="line">        <span class="keyword">if</span> ((e.hash &amp; bit) == <span class="number">0</span>) &#123;</span><br><span class="line">            <span class="keyword">if</span> ((e.prev = loTail) == <span class="literal">null</span>)</span><br><span class="line">                loHead = e;</span><br><span class="line">            <span class="keyword">else</span></span><br><span class="line">                loTail.next = e;</span><br><span class="line">            loTail = e;</span><br><span class="line">            ++lc;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">else</span> &#123;</span><br><span class="line">            <span class="keyword">if</span> ((e.prev = hiTail) == <span class="literal">null</span>)</span><br><span class="line">                hiHead = e;</span><br><span class="line">            <span class="keyword">else</span></span><br><span class="line">                hiTail.next = e;</span><br><span class="line">            hiTail = e;</span><br><span class="line">            ++hc;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">if</span> (loHead != <span class="literal">null</span>) &#123;</span><br><span class="line">        <span class="keyword">if</span> (lc &lt;= UNTREEIFY_THRESHOLD)</span><br><span class="line">            tab[index] = loHead.untreeify(map);</span><br><span class="line">        <span class="keyword">else</span> &#123;</span><br><span class="line">            tab[index] = loHead;</span><br><span class="line">            <span class="keyword">if</span> (hiHead != <span class="literal">null</span>) <span class="comment">// (else is already treeified)</span></span><br><span class="line">                loHead.treeify(tab);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span> (hiHead != <span class="literal">null</span>) &#123;</span><br><span class="line">        <span class="keyword">if</span> (hc &lt;= UNTREEIFY_THRESHOLD)</span><br><span class="line">            tab[index + bit] = hiHead.untreeify(map);</span><br><span class="line">        <span class="keyword">else</span> &#123;</span><br><span class="line">            tab[index + bit] = hiHead;</span><br><span class="line">            <span class="keyword">if</span> (loHead != <span class="literal">null</span>)</span><br><span class="line">                hiHead.treeify(tab);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>看起来有些复杂，其实和链表一样的。根据HASH将红黑树分出高低位链表来。再将两条链表树化塞入新的桶数组中。其中，有很多细节和特殊情况，暂不做讨论。关于红黑树的理论和实现，这里也不再详细赘述。</p>
<p>这样，对于HashMap是如何进行扩容的，我们有了一个基本的认识</p>

  </div>
</article>


    <div class="blog-post-comments">
        <div id="utterances_thread">
            <noscript>Please enable JavaScript to view the comments.</noscript>
        </div>
    </div>


        
          <div id="footer-post-container">
  <div id="footer-post">

    <div id="nav-footer" style="display: none">
      <ul>
         
          <li><a href="/">Home</a></li>
         
          <li><a href="/about/">About</a></li>
         
          <li><a href="/archives/">Articles</a></li>
         
          <li><a href="/categories/">Category</a></li>
         
          <li><a href="/search/">Search</a></li>
        
      </ul>
    </div>

    <div id="toc-footer" style="display: none">
      <ol class="toc"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E8%AE%A4%E8%AF%86HashMap"><span class="toc-number">1.</span> <span class="toc-text">认识HashMap</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%BA%95%E5%B1%82%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84"><span class="toc-number">1.1.</span> <span class="toc-text">底层数据结构</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%9E%84%E9%80%A0%E5%87%BD%E6%95%B0"><span class="toc-number">1.2.</span> <span class="toc-text">构造函数</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E9%97%A8%E9%99%90%E5%80%BC"><span class="toc-number">1.3.</span> <span class="toc-text">门限值</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%88%9D%E5%A7%8B%E5%8C%96%E5%AE%B9%E9%87%8F"><span class="toc-number">1.4.</span> <span class="toc-text">初始化容量</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E8%B4%9F%E8%BD%BD%E5%9B%A0%E5%AD%90"><span class="toc-number">1.5.</span> <span class="toc-text">负载因子</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%89%B0%E5%8A%A8%E5%87%BD%E6%95%B0"><span class="toc-number">1.6.</span> <span class="toc-text">扰动函数</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#HashMap%E5%9F%BA%E6%9C%AC%E6%93%8D%E4%BD%9C%E5%92%8C%E9%81%8D%E5%8E%86"><span class="toc-number">2.</span> <span class="toc-text">HashMap基本操作和遍历</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#4%E7%A7%8D%E9%81%8D%E5%8E%86%E6%96%B9%E5%BC%8F"><span class="toc-number">2.1.</span> <span class="toc-text">4种遍历方式</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%BA%95%E5%B1%82%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E7%9A%84%E6%9E%84%E5%BB%BA"><span class="toc-number">3.</span> <span class="toc-text">底层数据结构的构建</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E8%8A%82%E7%82%B9%E7%B1%BB"><span class="toc-number">3.1.</span> <span class="toc-text">节点类</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%8F%92%E5%85%A5%E8%8A%82%E7%82%B9%E7%9A%84putVal-%E6%96%B9%E6%B3%95"><span class="toc-number">3.2.</span> <span class="toc-text">插入节点的putVal()方法</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#%E5%81%9A%E5%A5%BD%E9%A2%84%E5%A4%87%E5%B7%A5%E4%BD%9C"><span class="toc-number">3.2.1.</span> <span class="toc-text">做好预备工作</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E7%AC%AC%E4%B8%80%E7%A7%8D%E6%83%85%E5%86%B5%EF%BC%88%E5%BD%93%E5%89%8D%E4%BD%8D%E7%BD%AE%E4%B8%BAnull%EF%BC%89"><span class="toc-number">3.2.2.</span> <span class="toc-text">第一种情况（当前位置为null）</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E7%AC%AC%E4%BA%8C%E7%A7%8D%E6%83%85%E5%86%B5%EF%BC%88hash%E5%88%86%E9%85%8D%E7%9A%84%E4%BD%8D%E7%BD%AE%E7%9B%B8%E5%90%8C%E4%B8%94Key%E7%9B%B8%E5%90%8C%EF%BC%89"><span class="toc-number">3.2.3.</span> <span class="toc-text">第二种情况（hash分配的位置相同且Key相同）</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E7%AC%AC%E4%B8%89%E7%A7%8D%E6%83%85%E5%86%B5%EF%BC%88%E5%8A%A0%E5%85%A5%E7%BA%A2%E9%BB%91%E6%A0%91%E8%8A%82%E7%82%B9%EF%BC%89"><span class="toc-number">3.2.4.</span> <span class="toc-text">第三种情况（加入红黑树节点）</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E7%AC%AC%E5%9B%9B%E7%A7%8D%E6%83%85%E5%86%B5%EF%BC%88%E5%8A%A0%E5%85%A5%E9%93%BE%E8%A1%A8%E8%8A%82%E7%82%B9%EF%BC%89"><span class="toc-number">3.2.5.</span> <span class="toc-text">第四种情况（加入链表节点）</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#HashMap%E7%9A%84resize-%E6%96%B9%E6%B3%95"><span class="toc-number">3.3.</span> <span class="toc-text">HashMap的resize()方法</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#%E6%97%A0%E5%8F%82%E6%9E%84%E9%80%A0%E7%9A%84%E7%A9%BAHashMap"><span class="toc-number">3.3.1.</span> <span class="toc-text">无参构造的空HashMap</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E8%BE%BE%E5%88%B0%E9%97%A8%E9%99%90%E5%80%BC%E9%9C%80%E8%A6%81%E6%89%A9%E5%AE%B9"><span class="toc-number">3.3.2.</span> <span class="toc-text">达到门限值需要扩容</span></a><ol class="toc-child"><li class="toc-item toc-level-5"><a class="toc-link" href="#%E6%95%B0%E7%BB%84%E7%9A%84%E8%B0%83%E6%95%B4"><span class="toc-number">3.3.2.1.</span> <span class="toc-text">数组的调整</span></a></li><li class="toc-item toc-level-5"><a class="toc-link" href="#%E9%93%BE%E8%A1%A8%E7%9A%84%E8%B0%83%E6%95%B4"><span class="toc-number">3.3.2.2.</span> <span class="toc-text">链表的调整</span></a></li><li class="toc-item toc-level-5"><a class="toc-link" href="#%E7%BA%A2%E9%BB%91%E6%A0%91%E7%9A%84%E8%B0%83%E6%95%B4"><span class="toc-number">3.3.2.3.</span> <span class="toc-text">红黑树的调整</span></a></li></ol></li></ol></li></ol></li></ol>
    </div>

    <div id="share-footer" style="display: none">
      <ul>
  <li><a class="icon" target="_blank" rel="noopener" href="http://www.facebook.com/sharer.php?u=https://cheung0-bit.github.io/d895167cf8d2/"><i class="fab fa-facebook fa-lg" aria-hidden="true"></i></a></li>
  <li><a class="icon" target="_blank" rel="noopener" href="https://twitter.com/share?url=https://cheung0-bit.github.io/d895167cf8d2/&text=HashMap"><i class="fab fa-twitter fa-lg" aria-hidden="true"></i></a></li>
  <li><a class="icon" target="_blank" rel="noopener" href="http://www.linkedin.com/shareArticle?url=https://cheung0-bit.github.io/d895167cf8d2/&title=HashMap"><i class="fab fa-linkedin fa-lg" aria-hidden="true"></i></a></li>
  <li><a class="icon" target="_blank" rel="noopener" href="https://pinterest.com/pin/create/bookmarklet/?url=https://cheung0-bit.github.io/d895167cf8d2/&is_video=false&description=HashMap"><i class="fab fa-pinterest fa-lg" aria-hidden="true"></i></a></li>
  <li><a class="icon" href="mailto:?subject=HashMap&body=Check out this article: https://cheung0-bit.github.io/d895167cf8d2/"><i class="fas fa-envelope fa-lg" aria-hidden="true"></i></a></li>
  <li><a class="icon" target="_blank" rel="noopener" href="https://getpocket.com/save?url=https://cheung0-bit.github.io/d895167cf8d2/&title=HashMap"><i class="fab fa-get-pocket fa-lg" aria-hidden="true"></i></a></li>
  <li><a class="icon" target="_blank" rel="noopener" href="http://reddit.com/submit?url=https://cheung0-bit.github.io/d895167cf8d2/&title=HashMap"><i class="fab fa-reddit fa-lg" aria-hidden="true"></i></a></li>
  <li><a class="icon" target="_blank" rel="noopener" href="http://www.stumbleupon.com/submit?url=https://cheung0-bit.github.io/d895167cf8d2/&title=HashMap"><i class="fab fa-stumbleupon fa-lg" aria-hidden="true"></i></a></li>
  <li><a class="icon" target="_blank" rel="noopener" href="http://digg.com/submit?url=https://cheung0-bit.github.io/d895167cf8d2/&title=HashMap"><i class="fab fa-digg fa-lg" aria-hidden="true"></i></a></li>
  <li><a class="icon" target="_blank" rel="noopener" href="http://www.tumblr.com/share/link?url=https://cheung0-bit.github.io/d895167cf8d2/&name=HashMap&description="><i class="fab fa-tumblr fa-lg" aria-hidden="true"></i></a></li>
  <li><a class="icon" target="_blank" rel="noopener" href="https://news.ycombinator.com/submitlink?u=https://cheung0-bit.github.io/d895167cf8d2/&t=HashMap"><i class="fab fa-hacker-news fa-lg" aria-hidden="true"></i></a></li>
</ul>

    </div>

    <div id="actions-footer">
        <a id="menu" class="icon" href="#" onclick="$('#nav-footer').toggle();return false;"><i class="fas fa-bars fa-lg" aria-hidden="true"></i> Menu</a>
        <a id="toc" class="icon" href="#" onclick="$('#toc-footer').toggle();return false;"><i class="fas fa-list fa-lg" aria-hidden="true"></i> TOC</a>
        <a id="share" class="icon" href="#" onclick="$('#share-footer').toggle();return false;"><i class="fas fa-share-alt fa-lg" aria-hidden="true"></i> Share</a>
        <a id="top" style="display:none" class="icon" href="#" onclick="$('html, body').animate({ scrollTop: 0 }, 'fast');"><i class="fas fa-chevron-up fa-lg" aria-hidden="true"></i> Top</a>
    </div>

  </div>
</div>

        
        <footer id="footer">
  <div class="footer-left">
    Copyright &copy;
      
        
          2022-2024
            <a target="_blank" rel="noopener" href="https://beian.miit.gov.cn/">
              苏ICP备2022044873号
            </a>
  </div>
  <div class="footer-right">
    <nav>
      <ul>
        
          <!--
       -->
          <li><a href="/">
              Home
            </a></li>
          <!--
     -->
          
          <!--
       -->
          <li><a href="/about/">
              About
            </a></li>
          <!--
     -->
          
          <!--
       -->
          <li><a href="/archives/">
              Articles
            </a></li>
          <!--
     -->
          
          <!--
       -->
          <li><a href="/categories/">
              Category
            </a></li>
          <!--
     -->
          
          <!--
       -->
          <li><a href="/search/">
              Search
            </a></li>
          <!--
     -->
          
      </ul>
    </nav>
  </div>
</footer>
    </div>
    <!-- styles -->


 
  <link
    rel="preload"
    href="/lib/font-awesome/css/all.min.css"
    as="style"
    onload="this.onload=null;this.rel='stylesheet'"
  />
  <noscript
    ><link
      rel="stylesheet"
      href="/lib/font-awesome/css/all.min.css"
  /></noscript>



    <!-- jquery -->
 
  
<script src="/lib/jquery/jquery.min.js"></script>





<!-- clipboard -->

   
    
<script src="/lib/clipboard/clipboard.min.js"></script>

  
  <script type="text/javascript">
  $(function() {
    // copy-btn HTML
    var btn = "<span class=\"btn-copy tooltipped tooltipped-sw\" aria-label=\"Copy to clipboard!\">";
    btn += '<i class="far fa-clone"></i>';
    btn += '</span>'; 
    // mount it!
    $(".highlight table").before(btn);
    var clip = new ClipboardJS('.btn-copy', {
      text: function(trigger) {
        return Array.from(trigger.nextElementSibling.querySelectorAll('.code')).reduce((str,it)=>str+it.innerText+'\n','')
      }
    });
    clip.on('success', function(e) {
      e.trigger.setAttribute('aria-label', "Copied!");
      e.clearSelection();
    })
  })
  </script>


<script src="/js/main.js"></script>

<!-- search -->

<!-- Google Analytics -->

<!-- Baidu Analytics -->

  <script type="text/javascript">
        var _hmt = _hmt || [];
        (function() {
          var hm = document.createElement("script");
          hm.src = "https://hm.baidu.com/hm.js?4484a4a33014b59670c470a6e15a66db";
          var s = document.getElementsByTagName("script")[0];
          s.parentNode.insertBefore(hm, s);
        })();
        </script>

<!-- Cloudflare Analytics -->

<!-- Umami Analytics -->

<!-- Disqus Comments -->

<!-- utterances Comments -->

    <script type="text/javascript">
      var utterances_repo = 'Cheung0-bit/blog-package';
      var utterances_issue_term = 'title';
      var utterances_label = 'Comment';
      var utterances_theme = 'github-dark';

      (function(){
          var script = document.createElement('script');

          script.src = 'https://utteranc.es/client.js';
          script.setAttribute('repo', utterances_repo);
          script.setAttribute('issue-term', 'pathname');
          script.setAttribute('label', utterances_label);
          script.setAttribute('theme', utterances_theme);
          script.setAttribute('crossorigin', 'anonymous');
          script.async = true;
          (document.getElementById('utterances_thread')).appendChild(script);
      }());
  </script>

</body>
</html>
